// 双向队列存下标
function ts_main1(nums: number[], k: number): number[] {
  const len = nums.length;
  if (len === 1 || k === 1) return nums;
  const result: number[] = [];
  const queue: number[] = [];
  const width = k - 1;
  for (let right = 0; right < len; right++) {
    while(queue.length && nums[right] >= nums[queue[queue.length-1]]){
      queue.pop();
    }
    queue.push(right);
    if (right >= width) {
      const left = right - width; // 包含right，所以left要+1
      if (queue[0] < left) {
        queue.shift();
      }
      result[left] = nums[queue[0]];
    }
  }
  return result;
}

console.log(ts_main1([1, 3, -1, -3, 5, 3, 6, 7], 3));
console.log(ts_main1([1], 1));
console.log(ts_main1([1, -1], 1));
console.log(ts_main1([9, 11], 2));
console.log(ts_main1([4, -2], 2));

// 双向队列存值
function ts_main2(nums: number[], k: number): number[] {
  const len = nums.length;
  if (len === 1 || k === 1) return nums;
  const queue: number[] = [];
  const result: number[] = [];
  const width = k - 1;
  for (let right = 0; right < len; right++) {
    while (queue.length && queue[queue.length - 1] < nums[right]) {
      // 该循环能保证队列前面元素的下标一定在其后元素的左侧
      queue.pop();
    }
    queue.push(nums[right]);
    if (right >= width) { // 滑动窗口
      result.push(queue[0]); // 将最大值push到结果数组
      // 判断窗口最后一位元素是否最大值，如果是则移除，保证下一次窗口移动时不会有跃出边界的值
      if (queue[0] === nums[right - width]) {
        queue.shift();
      }
    }
  }
  return result;
}

console.log(ts_main2([1, 3, -1, -3, 5, 3, 6, 7], 3));
console.log(ts_main2([1], 1));
console.log(ts_main2([1, -1], 1));
console.log(ts_main2([9, 11], 2));
console.log(ts_main2([4, -2], 2));
